#include <stdio.h>
#include <stdlib.h>

// AI
#define RED 0
#define BLACK 1

typedef struct Node {
    int data;
    int color;
    struct Node *left, *right, *parent;
} Node;

typedef struct RBTree {
    Node *root;
    Node *TNULL;
} RBTree;

// 创建一个新的节点
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->color = RED;  // 新节点总是红色
    node->left = node->right = node->parent = NULL;
    return node;
}

// 左旋操作
void leftRotate(RBTree *tree, Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left != tree->TNULL)
        y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL)
        tree->root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

// 右旋操作
void rightRotate(RBTree *tree, Node *x) {
    Node *y = x->left;
    x->left = y->right;
    if (y->right != tree->TNULL)
        y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL)
        tree->root = y;
    else if (x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;
    y->right = x;
    x->parent = y;
}

// 插入修复操作
void fixInsert(RBTree *tree, Node *k) {
    Node *u;
    while (k->parent->color == RED) {
        if (k->parent == k->parent->parent->right) {
            u = k->parent->parent->left;
            if (u->color == RED) {
                u->color = BLACK;
                k->parent->color = BLACK;
                k->parent->parent->color = RED;
                k = k->parent->parent;
            } else {
                if (k == k->parent->left) {
                    k = k->parent;
                    rightRotate(tree, k);
                }
                k->parent->color = BLACK;
                k->parent->parent->color = RED;
                leftRotate(tree, k->parent->parent);
            }
        } else {
            u = k->parent->parent->right;
            if (u->color == RED) {
                u->color = BLACK;
                k->parent->color = BLACK;
                k->parent->parent->color = RED;
                k = k->parent->parent;
            } else {
                if (k == k->parent->right) {
                    k = k->parent;
                    leftRotate(tree, k);
                }
                k->parent->color = BLACK;
                k->parent->parent->color = RED;
                rightRotate(tree, k->parent->parent);
            }
        }
        if (k == tree->root)
            break;
    }
    tree->root->color = BLACK;
}

// 插入节点
void insert(RBTree *tree, int key) {
    Node *node = newNode(key);
    Node *y = NULL;
    Node *x = tree->root;

    while (x != tree->TNULL) {
        y = x;
        if (node->data < x->data)
            x = x->left;
        else
            x = x->right;
    }

    node->parent = y;
    if (y == NULL)
        tree->root = node;
    else if (node->data < y->data)
        y->left = node;
    else
        y->right = node;

    node->left = node->right = tree->TNULL;
    fixInsert(tree, node);
}

// 初始化红黑树
RBTree* createRBTree() {
    RBTree *tree = (RBTree*)malloc(sizeof(RBTree));
    tree->TNULL = newNode(0);  // NIL节点
    tree->TNULL->color = BLACK;
    tree->root = tree->TNULL;
    return tree;
}

// 中序遍历树
void inorderHelper(Node *root, Node *TNULL) {
    if (root != TNULL) {
        inorderHelper(root->left, TNULL);
        printf("%d ", root->data);
        inorderHelper(root->right, TNULL);
    }
}

// 中序遍历
void inorder(RBTree *tree) {
    inorderHelper(tree->root, tree->TNULL);
}

int main() {
    RBTree *tree = createRBTree();

    insert(tree, 10);
    insert(tree, 20);
    insert(tree, 30);
    insert(tree, 15);

    printf("Inorder Traversal: ");
    inorder(tree);
    printf("\n");

    return 0;
}
